home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 9393 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.1 KB
  1. Path: aux82.plano.net!user
  2. From: richmond@plano.net (Charles Richmond)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Best Binary Search Tree Balance Algo?
  5. Date: 10 Mar 1996 05:57:23 GMT
  6. Organization: Canine Organization
  7. Message-ID: <richmond-0903962355070001@aux82.plano.net>
  8. References: <4hqvc5$p9k@solaria.cc.gatech.edu>
  9. NNTP-Posting-Host: aux82.plano.net
  10.  
  11. In article <4hqvc5$p9k@solaria.cc.gatech.edu>, bigdave@cc.gatech.edu
  12. (David Mitchell) wrote:
  13. > I would like to know what the run-time of the best binary search tree 
  14. > balance algorithm is.  (e.g. O(n^2), O(n lg n), etc.).
  15. > 
  16. I believe the AVL balanced tree algorithm is the fastest. It works in
  17. big-O of log base 2 of n. The red/black balanced tree algorithm is
  18. *almost* as good. It works in the same big-O time, but has larger constant
  19. terms in the performance equation.
  20.  
  21. Because you asked about binary trees, you are ruling out 2-3 B-trees and
  22. 2-4 B-trees. However, I do *not* think any of these beat the performance
  23. of the AVL algorithm. They work better when some of the data exists on
  24. disk and must be swapped into memory.
  25.